// ------------------------------------------------------------------------------------------------
// ---- Livro Algoritmos (de Dasgupta, Vazirani, Papadimitriou) -----------------------------------
// ---- Problema da MOCHILA (Capítulo 6.4) --------------------------------------------------------
// ------------------------------------------------------------------------------------------------
#include <iostream>
using namespace std;

int mochila(int* peso, int* valor, int N, int W, bool repet);

// -------------------------------------------------------------
// --- MAIN ----------------------------------------------------
// -------------------------------------------------------------
int main() {
    const int N = 5;
    int peso[N] = {1,1,2,4,12};
    int valor[N] = {1,2,2,10,4};
    int W = 15; // capacidade da mochila

    cout << "Valor maximo com repeticao: " << mochila(peso,valor,N,W,true) << "\n";
    cout << "Valor maximo sem repeticao: " << mochila(peso,valor,N,W,false) << "\n";
    return 0;
}

int mochila(int* peso, int* valor, int N, int W, bool repet) {
    int i, w;
    if (repet)
    {
        int* V = new int[W+1];
        V[0] = 0;
        for (w=1; w<=W; w++) {
            V[w] = 0;
            for (i=0; i<N; i++) {
                if ((peso[i]<=w) && (V[w] < V[w-peso[i]]+valor[i]))
                    V[w] = V[w-peso[i]] + valor[i];
            }
        }
        int r = V[W];
        delete[] V;
        return r;
    }
    else
    {
        int** V = new int*[N+1];
        for (i=0; i<=N; i++) V[i] = new int[W+1];
        for (w=0; w<=W; w++) V[0][w] = 0;

        for (i=1; i<=N; i++) {
            for (w=0; w<=W; w++) {
                V[i][w] = V[i-1][w];
                if ((peso[i-1]<=w) && (V[i][w] < V[i-1][w-peso[i-1]] + valor[i-1])) {
                    V[i][w] = V[i-1][w-peso[i-1]] + valor[i-1];
                }
            }
        }
        int r = V[N][W];
        for (i=0; i<=N; i++) delete[] V[i];
        delete[] V;
        return r;
    }
}